package 力扣._00周赛._428周赛.问题2;

import java.util.*;

class Solution {

    // dfs
    void dfs(int i, double[][] graph, int[] visited, double[] rate,double now_rate, int last_index) {
        visited[i] = 1;
        rate[i] = now_rate * graph[last_index][i];
        for (int j = 0; j < graph.length; j++) {
            if (graph[i][j] != 0 && visited[j] == 0) {
                dfs(j, graph, visited, rate,rate[i], i);
            }
        }
    }

    public double maxAmount(String initialCurrency,
                            List<List<String>> pairs1, double[] rates1,
                            List<List<String>> pairs2, double[] rates2
    ) {
        List<String> currencies = new ArrayList<>();
        currencies.add(initialCurrency);
        for (List<String> pair : pairs1) {
            if(!currencies.contains(pair.get(0))){
                currencies.add(pair.get(0));
            }
            if(!currencies.contains(pair.get(1))){
                currencies.add(pair.get(1));
            }
        }
        for (List<String> pair : pairs2) {
            if(!currencies.contains(pair.get(0))){
                currencies.add(pair.get(0));
            }
            if(!currencies.contains(pair.get(1))){
                currencies.add(pair.get(1));
            }
        }
        int n = currencies.size();
        System.out.println(currencies);
        // 先计算第一天初始货币对其他货币的汇率 a



        // 创建图，将货币对作为节点，汇率作为边，然后DFS找到初始货币对其他货币的汇率
        double[][] graph = new double[n][n];
        for (int k = 0; k < pairs1.size(); k++) {
            List<String> pair = pairs1.get(k);
            int i = currencies.indexOf(pair.get(0));
            int j = currencies.indexOf(pair.get(1));
            graph[i][j] = rates1[k];
            graph[j][i] = 1 / rates1[k];
        }
        for (int i = 0; i < n; i++) {
            graph[i][i] = 1;
        }
        double[] rate_1 = new double[n];
        // DFS
        int[] visited = new int[n];
        int initial_index = currencies.indexOf(initialCurrency);
        dfs(initial_index, graph, visited, rate_1,1,initial_index);

        System.out.println(Arrays.toString(rate_1));

        // 再计算第二天其他货币对初始货币的汇率 b
        double[][] graph2 = new double[n][n];
        for (int k = 0; k < pairs2.size(); k++) {
            List<String> pair = pairs2.get(k);
            int i = currencies.indexOf(pair.get(0));
            int j = currencies.indexOf(pair.get(1));
            graph2[i][j] = rates2[k];
            graph2[j][i] = 1 / rates2[k];
        }
        for (int i = 0; i < n; i++) {
            graph2[i][i] = 1;
        }
        double[] rate_2 = new double[n];
        // DFS
        int[] visited2 = new int[n];
        dfs(initial_index, graph2, visited2, rate_2,1,initial_index);
        System.out.println(Arrays.toString(rate_2));

        // 找到最大的 a * b, 若 a * b > 1, 则返回则第一天全部兑换成指定货币，第二天再全部兑换回来
        double max = 0;
        for (int i = 0; i < n; i++) {
            if(rate_2[i] == 0){
                continue;
            }
            max = Math.max(max, rate_1[i] / rate_2[i]);
        }

        return max;
    }

    public static void main(String[] args) {
        // "EUR"
        //[["EUR","USD"],["USD","JPY"]]
        //[2.0,3.0]
        //[["JPY","USD"],["USD","CHF"],["CHF","EUR"]]
        //[4.0,5.0,6.0]©leetcode
        Solution solution = new Solution();
//        double v = solution.maxAmount(
//                "EUR",
//                Arrays.asList(Arrays.asList("EUR", "USD"), Arrays.asList("USD", "JPY")),
//                new double[]{2.0, 3.0},
//                Arrays.asList(Arrays.asList("JPY", "USD"), Arrays.asList("USD", "CHF"), Arrays.asList("CHF", "EUR")),
//                new double[]{4.0, 5.0, 6.0}
//        );
        // "USD"
        //[["USD","EUR"]]
        //[1.0]
        //[["EUR","JPY"]]
        //[10.0]©leetcode
        double v = solution.maxAmount(
                "USD",
                Arrays.asList(Arrays.asList("USD", "EUR")),
                new double[]{1.0},
                Arrays.asList(Arrays.asList("EUR", "JPY")),
                new double[]{10.0}
        );
        System.out.println(v);

    }
}